COMP3141
Software System Design and Implementation (18s1)

Exercise (Week 10)

Table of Contents

Ex08-icon.gif

DUE: 13 May, 2018 23:55

Download the exercise tarball and extract it to a directory in your home directory at CSE. This tarball contains a file, called Ex08.hs, wherein you will do all of your programming.

To test your code, run the following shell commands to open a GHCi session: 

$ 3141
newclass starting new subshell for class COMP3141...
$ cabal repl
Resolving dependencies...
Configuring Ex08-1.0...
Preprocessing executable 'Ex08' for Ex08-1.0..
GHCi, version 8.2.2: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Ex08          (Ex08.hs, interpreted)
Ok, one module loaded.
*Ex08> flights SSydney SSeoul
...

Note that you will only need to submit Ex08.hs, so only make changes to that file.

Download the exercise tarball and extract it to a directory on your local machine. This tarball contains a file, called Ex08.hs, wherein you will do all of your programming.

To test your code, run the following shell commands to open a GHCi session: 

$ stack repl
Configuring GHCi with the following packages: Ex08
Using main module: 1. Package 'Ex08' component exe:Ex08 ...
GHCi, version 8.2.2: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Ex08          (Ex08.hs, interpreted)
Ok, one module loaded.
*Ex08> flights SSydney SSeoul
...

Note that you will only need to submit Ex08.hs, so only make changes to that file.

Download the Haskell for Mac project and unzip it somewhere on your local machine. Open the project in Haskell for Mac, and begin coding in Ex08.hs.

Note that you will only need to submit Ex08.hs, so only make changes to that file.

1 Flight Planning System

In this exerise, we will work on a basic flight planning system to organise journeys between various sibilant cities in the eastern hemisphere: 

data City = Sydney | Shanghai | Seoul | Singapore | Sapporo 
          deriving (Eq, Show, Enum)

allCities :: [City]
allCities = [Sydney ..]

We shall also define a singleton type version of City using the following GADT definition, allowing us to connect the type level to the value level: 

data SCity :: City -> * where
  SSydney    :: SCity Sydney
  SShanghai  :: SCity Shanghai
  SSeoul     :: SCity Seoul
  SSingapore :: SCity Singapore
  SSapporo   :: SCity Sapporo

Note that because the only inhabitant of, for example, SCity Sydney is SSydney, this allows us to determine which type the parameter of SCity is by pattern matching on its value.

We also define a function to throw away the type level information and return the regular City corresponding to an SCity: 

untype :: SCity s -> City
untype SSydney    = Sydney
untype SShanghai  = Shanghai
untype SSeoul     = Seoul
untype SSingapore = Singapore
untype SSapporo   = Sapporo

And, for the other direction, we use Rank-N types to define a function that, given a function that works on any of the singleton SCity types, converts it to a function that operates on untyped City values: 

withTyped :: (forall c. SCity c -> b) -> City -> b
withTyped f Sydney    = f SSydney
withTyped f Shanghai  = f SShanghai
withTyped f Seoul     = f SSeoul
withTyped f Singapore = f SSingapore
withTyped f Sapporo   = f SSapporo

Our flight system knows about the following flights, and their starting and finishing points are encoded in their type: 

data Flight :: City -> City -> * where
  NH880 :: Flight Sydney Sapporo
  SQ222 :: Flight Sydney Singapore
  KE122 :: Flight Sydney Seoul
  KE121 :: Flight Seoul Sydney
  SQ825 :: Flight Shanghai Singapore
  SQ231 :: Flight Singapore Sydney
  KE893 :: Flight Seoul Shanghai

A Journey could consist of a single direct flight, or multiple journeys joined together at a common stop-over point. Note that the type variable b here is effectively existentially quantified as it does not appear in the return type: 

data Journey :: City -> City -> * where
  Fly :: Flight a b -> Journey a b
  Connect :: Journey a b -> Journey b c -> Journey a c

1.1 Part 1 - flight (3 marks)

Implement a function that, given two SCity values, returns a flight that connects these two cities, if one exists, or Nothing otherwise. 

flight :: SCity a -> SCity b -> Maybe (Flight a b)

1.2 Part 2 - journeys (6 marks)

Implement the function journeys, type signature as below: 

journeys :: [City] -> SCity a -> SCity b -> [Journey a b]

journeys cs a b returns all journeys starting in a and ending in b, starting with the most direct one, which can make intermediate stops only at cities listed in cs.

Examples: 

*Ex08> journeys [Shanghai, Singapore] SSeoul SSydney
[Fly KE121
,Connect (Fly KE893) (Connect (Fly SQ825) (Fly SQ231))
,Connect (Connect (Fly KE893) (Fly SQ825)) (Fly SQ231)
]

*Ex08> journeys [Sydney, Singapore] SSingapore SSydney
[Fly SQ231
,Connect (Fly SQ231) (Connect (Fly SQ222) (Fly SQ231))
,Connect (Connect (Fly SQ231) (Fly SQ222)) (Fly SQ231)
]

The list you must return will consist of:

  • The direct flight, if one exists, from the starting point to the ending point.
  • For each city c in the given list of stop-over cities, every journey from the starting point to c (with c removed from the list of stop-overs), Connect-ed to every journey from c to the ending point. List comprehensions can be used to some effect here. Also, the function delete from Data.List can be used to remove the city from the list of stop-overs on each recursive call. Use the untype and withTyped functions to convert between the singleton SCity and the plain City as needed.

2 Submission instructions

$ give cs3141 Ex08 Ex08.hs

on a CSE terminal, or by using the give web interface. Your file must be named Ex08.hs (case-sensitive!). A dry-run test will partially autotest your solution at submission time. To get full marks, you will need to perform further testing yourself.

2018-06-14 Thu 18:29

Announcements RSS